In the context of electrical/electronic circuit design, interconnect routing (also referred to as “routing”) refers to a process of developing a layout of wires and vias to create circuit connections among circuit components. A via is a vertical conductor to connect different layers of a circuit assembly, e.g., a plated through-hole. A wire, or trace, is a horizontal conductor to connect circuit components on a single layer of a circuit assembly. Routing is a very important step in a design flow because this is the step that translates a logical connectivity of a netlist, which describes how circuit elements are logically interconnected, into a physical connectivity by finding the right locations and the right layers on which to place actual conductive interconnections (e.g., wires and vias). The complexity of a routing process is dependent on the size of the design circuit, i.e., the number of gates in the design, and the design area. As the number of gates grows while the design area remains the same or becomes smaller, the complexity of a routing process increases significantly.
A routing engine (also referred to as a “router”) refers to an algorithm or a collection of algorithms used to solve the routing problem. There are two main requirements for a routing engine. First, the routing solution must be DRC (design rule check) clean, which means that the wires and vias that are outlined by the router must not violate the relevant design rules. With routing being an iterative process, some design rule violations may be tolerated at intermediate stages of computation; however, the goal of a good router is to ultimately produce a DRC clean design. Such design rules are driven by manufacturing process constraints, which include minimum spacing requirements, minimum size requirements, and other requirements that must be met in order to have a working circuit. Each design rule is typically directed to a particular object type pair, which could be positioned on different layers of a circuit assembly, and where each unique object type is a certain type of circuit component or interconnect element with a corresponding shape and orientation. Second, the router must complete the routing in a reasonable amount of time and, therefore, computational runtime is an important factor. A fast router that can produce a DRC clean solution is the most preferable router.
In general, a routing algorithm comprises two main components: (a) a search engine and (b) a marking engine. The search engine is a component that searches for an available path for each net, where the set of available paths are limited, for example, by manufacturing constraints. The marking engine is a component that verifies the validity of that path against one or more applicable design rules and, effectively, guides the search engine by limiting the possible paths that may be used to connect two or more circuit components. A technique used for guiding the search engine is referred to as “marking.” In the past, the search engine was the component that consumed most of the routing runtime. However, with the rapid and significant increase in the number of design rules for newer process technologies, the marking engine has become the main bottleneck in the routing process due to the large number of rules that need to be checked.
Every circuit interconnect element is associated with a corresponding shaped area that the element consumes on a circuit assembly. A traditional approach for performing DRC during a marking phase is by expanding the area required of a given circuit interconnect element to include its required spacing distance (the expanded area is referred to herein as “the violation area”) and by marking the violation area for any possibility of violation introduced by another circuit interconnect element if this other element's area overlaps the given element's area. For a given point inside that violation area, several calculations are made for all possible circuit interconnect elements that can be placed at that point. With the rapid increase in the number of vias that can be used in circuit designs, the number of possible circuit interconnect elements for a given point increases accordingly. Thus, the routing runtime could degrade significantly.
In a typical routing process, DRC marking is performed by considering certain points in the vicinity of each circuit interconnect element area and computing a potential DRC violation at each point if a specific circuit interconnect element is placed at that point. Due to the large number of viable points in the vicinity of each element, the router spends a significant amount of time performing the marking process.
Based on the foregoing, there is a need for a faster and more computationally efficient interconnect routing process in the context of circuit design.